n=100
#递归会超时
def fib(n: int) -> int:
    if n==0:
        return 0
    if n==1:
        return 1

    return int((fib(n-1)+fib(n-2))%(1e9+7))


def fib1(n):
    if n==0:
        return 0
    if n==1:
        return 1

    dp=[0 for _ in range(n+1)]
    dp[0]=0
    dp[1]=1

    for i in range(2,n+1):
        dp[i]=int((dp[i-1]+dp[i-2])%(1e9+7))
    return dp[n]


    pass
print(fib1(n))